Microprocessor designers employ many techniques to increase microprocessor performance. Most microprocessors operate using a clock signal running at a fixed frequency. Each clock cycle the circuits of the microprocessor perform their respective functions. According to Hennessy and Patterson (see Computer Architecture: A Quantitative Approach, 3rd Edition), the true measure of a microprocessor's performance is the time required to execute a program or collection of programs. From this perspective, the performance of a microprocessor is a function of its clock frequency, the average number of clock cycles required to execute an instruction (or alternately stated, the average number of instructions executed per clock cycle), and the number of instructions executed in the program or collection of programs. Semiconductor scientists and engineers are continually making it possible for microprocessors to run at faster clock frequencies, chiefly by reducing transistor size, resulting in faster switching times. The number of instructions executed is largely fixed by the task to be performed by the program, although it is also affected by the instruction set architecture of the microprocessor. Large performance increases have been realized by architectural and organizational notions that improve the instructions per clock cycle, in particular by notions of parallelism.
One notion of parallelism that has improved the instructions per clock cycle, as well as the clock frequency, of microprocessors is pipelining, which overlaps execution of multiple instructions within pipeline stages of the microprocessor. In an ideal situation, each clock cycle one instruction moves down the pipeline to a new stage, which performs a different function on the instruction. Thus, although each individual instruction takes multiple clock cycles to complete, because the multiple cycles of the individual instructions overlap, the average clocks per instruction is reduced. The performance improvements of pipelining may be realized to the extent that the instructions in the program permit it, namely to the extent that an instruction does not depend upon its predecessors in order to execute and can therefore execute in parallel with its predecessors, which is commonly referred to as instruction-level parallelism. Another way in which instruction-level parallelism is exploited by contemporary microprocessors is the issuing of multiple instructions for execution per clock cycle. These microprocessors are commonly referred to as superscalar microprocessors.
What has been discussed above pertains to parallelism at the individual instruction-level. However, the performance improvement that may be achieved through exploitation of instruction-level parallelism is limited. Various constraints imposed by limited instruction-level parallelism and other performance-constraining issues have recently renewed an interest in exploiting parallelism at the level of blocks, or sequences, or streams of instructions, commonly referred to as thread-level parallelism. A thread is simply a sequence, or stream, of program instructions. A multithreaded microprocessor concurrently executes multiple threads according to some scheduling policy that dictates the fetching and issuing of instructions of the various threads, such as interleaved, blocked, or simultaneous multithreading. A multithreaded microprocessor typically allows the multiple threads to share the functional units of the microprocessor (e.g., instruction fetch and decode units, caches, branch prediction units, and load/store, integer, floating-point, SIMD, etc. execution units) in a concurrent fashion. However, multithreaded microprocessors include multiple sets of resources, or contexts, for storing the unique state of each thread, such as multiple program counters and general purpose register sets, to facilitate the ability to quickly switch between threads to fetch and issue instructions.
One example of a performance-constraining issue addressed by multithreading microprocessors is the fact that accesses to memory outside the microprocessor that must be performed due to a cache miss typically have a relatively long latency. It is common for the memory access time of a contemporary microprocessor-based computer system to be between one and two orders of magnitude greater than the cache hit access time. Instructions dependent upon the data missing in the cache are stalled in the pipeline waiting for the data to come from memory. Consequently, some or all of the pipeline stages of a single-threaded microprocessor may be idle performing no useful work for many clock cycles. Multithreaded microprocessors may solve this problem by issuing instructions from other threads during the memory fetch latency, thereby enabling the pipeline stages to make forward progress performing useful work, somewhat analogously to, but at a finer level of granularity than, an operating system performing a task switch on a page fault. Other examples of performance-constraining issues addressed by multithreading microprocessors are pipeline stalls and their accompanying idle cycles due to a data dependence; or due to a long latency instruction such as a divide instruction, floating-point instruction, or the like; or due to a limited hardware resource conflict. Again, the ability of a multithreaded microprocessor to issue instructions from other threads to pipeline stages that would otherwise be idle may significantly reduce the time required to execute the program or collection of programs comprising the threads.
Because there are multiple threads in a multithreading processor competing for limited resources, such as instruction fetch and execution bandwidth, there is a need to fairly arbitrate among the threads for the limited resources. One fair arbitration scheme used in other contexts is a round-robin arbitration scheme. In a round-robin arbitration scheme, an order of the requestors is maintained and each requestor gets a turn to use the requested resource in the maintained order. The circuitry to implement a round-robin arbitration scheme in which each of the requesters requests the resource each time the resource becomes available is not complex. A conventional round-robin circuit may be implemented as a simple N-bit barrel shifter, wherein N is the number of requesters and one bit corresponds to each of the N requesters. One bit of the barrel shifter is initially true, and the single true bit is rotated around the barrel shifter each time a new requestor is selected. One characteristic of such a round-robin circuit is that the complexity is N. In particular, the integrated circuit area and power consumed by the barrel shifter grows linearly with the number of requestors N.
However, the circuitry to implement a round-robin arbitration scheme in which only a variable subset of the requestors may be requesting the resource each time the resource becomes available is more complex. A conventional round-robin circuit accommodating a variable subset of requesting requesters may be implemented by a storage element storing an N-bit vector, denoted L, having one bit set corresponding to the previously selected requestor and combinational logic receiving the L vector and outputting a new N-bit selection vector, denoted N, according to the following equation, where E.i indicates whether a corresponding one of the requestors is currently requesting:
N.i =; This requestor is enabled, i.e., is requesting. E.i AND; The requestor to the right was selected last time. (L.i−1 OR; A requestor further to the right was selected last; time AND the requestors in between are disabled. (~E.i−1 AND L.i−2) OR (~E.i−1 AND ~E.i−2 AND L.i−3) OR ...; This requestor was selected last time,; but no other requestors are enabled. (~E.i−1 AND ~E.i−2 AND ~E.i−3 AND . . . ~E.i+1 AND L.i))
As may be observed from the equation above, the complexity of the conventional round-robin circuit accommodating a variable subset of disabled requestors has complexity N2. Thus, as the number of requesters—such as the number of threads in a multithreading microprocessor—becomes relatively large, the size of the conventional circuit may become burdensome on the processor in terms of size and power consumption, particularly if more than one such circuit is needed in the processor. Therefore, what is needed is a round-robin apparatus and method that accommodates a variable subset of all requestors requesting at a time, which has reduced complexity over a conventional circuit.
Furthermore, in some applications, the requestors may have multiple priority levels; i.e., some requestors may have higher priority than others. It is desirable to select requestors fairly within each of the priority levels. That is, it is desirable for requesters to be chosen in a round-robin manner within each priority level independent of the order requestors are chosen within the other priority levels. Furthermore, the priority levels of the various requestors may change dynamically over time. Therefore, what is also needed is a simple and fast round-robin apparatus and method that accommodates a variable subset of all requestors requesting at a time, and which does so independent of the priority level, among multiple priority levels, at which the requesters are requesting.
Finally, a particular application in which the requestors may have multiple priority levels is in a dispatch scheduler in a multithreaded microprocessor. Therefore, what is also needed is a simple and fast round-robin apparatus and method that accommodates a variable subset of all threads requesting instruction dispatch at a time, and which does so independent of the priority level, among multiple priority levels, at which the threads are requesting to be dispatched.